/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <queue> 
#include <stack>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace boost;   // 支持string的操作
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

// 遍历
template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit_arr(vector<T>& arr, string const str){
    cout << str << ": ";
    for(auto it=arr.begin();it!=arr.end();++it){
        cout << *it <<" ";
    }
    cout<<endl;
}
// 遍历
// template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit2_arr(vector<int>& arr, string const str){
    cout << str << ": ";
    for(int i; i < arr.size(); ++i){
        cout << arr[i] << " ";
    }
    cout<<endl;
}



// 链表结点
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void visit_list(ListNode* head){
    ListNode* tmp = head;
    while(tmp != nullptr){
        cout << tmp->val << ' ';
        tmp = tmp->next;
    }
    cout << endl;
}

// 二叉树--孩子兄弟表示法
//Definition for a binary tree node.// 二叉树--孩子兄弟表示法
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

//dp+回溯
class Solution {
public:
    int n;
    vector<string> path;
    vector<vector<string>> ans;
    vector<vector<string>> partition(string s) {
        n = s.size();
        // 用于判断是否为回文子串----动态规划---dp[i][j]表示从i到j的字符串是回文子串
        vector<vector<bool>> dp(n,vector<bool>(n,true));
        for(int l = 2; l <= n; l ++)  // 为什么从2开始
            for(int i = 0,j = i+l-1; j < n; i++,j++)
                dp[i][j] = (s[i]==s[j]) && dp[i+1][j-1];
        
        dfs(dp,0,s);
        return ans;
    }
    void dfs(vector<vector<bool>>& dp,int i,string s){
        // i为startIndex
        if(i == n) ans.push_back(path);
        for(int j = i; j < n; j++)
            if(dp[i][j]){
                path.emplace_back(s.substr(i,j+1-i));  //相比push_back更加高效  http://c.biancheng.net/view/6826.html
                dfs(dp,j+1,s);
                path.pop_back();
            }
    }
};

// class Solution {
// public:
//     vector<vector<string>> partition(string s) {
//         vector<vector<string>> ans;
//         int slow = 0, len = 0;
//         int maxLen = s.length();
//         for (slow = 0; slow < s.length(); slow++) {
//             for (len = 1; len <= s.length() - slow; len++) {
//                 if (isPalindrome(s.substr(slow, len))) {
//                     vector<string> tmp = {s.substr(slow, len)};
//                     ans.push_back(tmp);
//                 }
//             }
//         }
//         return ans;
//     }

//     // 验证回文串
//     bool isPalindrome(string s) {
//         // tolower(s); // 转换为小写
//         // if (s.length()==1) return isalnum(s[0]) || s[0]==' ';
//         if (s.length()==1) return true;
//         int start = 0;
//         int end = s.length()-1;
//         while(start < end) {
//             for(;!isalnum(s[start]) && start < end; ++start);
//             for(;!isalnum(s[end]) && start < end; --end);
//             if(isalpha(s[start])) s[start] = tolower(s[start]);
//             if(isalpha(s[end])) s[end] = tolower(s[end]);
//             cout << start << " " << s[start] << endl;
//             cout << end << " " << s[end] << endl;
//             if (s[start] != s[end]) return false; 
//             else{
//                 start++;
//                 end--;
//             }
//         }
//         return true;
//     }
// };


int main(int argc, const char** argv) {
    Solution solu = Solution();
    // 常见边界值
    // cout << INT32_MAX << endl;
    // cout << INT32_MIN << endl;
    // cout << INT_MAX << endl;
    // cout << INT_MIN << endl;
    string s = "hello";
    cout << s.substr(0,1) << endl;
    time_t start = time(NULL);
    cout << "start time is " << start << endl;

    vector<vector<string>> ans = solu.partition(s);
    for (auto i = ans.begin(); i != ans.end();++i) {
        visit_arr<string>((*i), "");
    }
    // cout << solu.minSubArrayLen(target, nums) << endl;
    
    time_t end = time(NULL);
    cout << "end time is " << start << endl;
    cout << "耗时：" << end*100-start*100 << " s." <<endl;


    return 0;
}